public class UniquePaths {
    // 不同路径的数目
    // https://www.nowcoder.com/practice/166eaff8439d4cd898e3ba933fbc6358?tpId=295&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3DSQL%25E7%25AF%2587%26topicId%3D295
    public int uniquePaths (int m, int n) {
        // write code here
        // dp[i][j]表示走到(i,j)的位置有多少种走法
        // dp[i][j] = dp[i-1][j] + dp[i][j-1]
        int[][] dp = new int[m+1][n+1];
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m][n];
    }

    public int uniquePaths1 (int m, int n) {
        // write code here
        // 空间优化，因为在填dp[i][j]的时候只使用到了dp[i-1][j]和dp[i][j-1]
        // 所以可以使用一维数组来进行空间优化
        // 那么填表的顺序就是从上到下、从左到右
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[j] = dp[j] + dp[j-1];
            }
        }
        return dp[n];
    }
}
